

#子问题的重复计算
def fibnacci(n):
    if n==1 or n==2:
        return 1
    return fibnacci(n-1)+fibnacci(n-2)

#动态规划（DP）的思想=递推式+重复子问题
def fibnacci_no_recurision(n):
    f=[0,1,1]
    if n>2:
        for i in range(n-2):
            f.append(f[-1]+f[-2])
    return f[-1]

print(fibnacci(5))
print(fibnacci_no_recurision(50))